package com.xiaoyg.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InorderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode roo1 = new TreeNode(2);
        TreeNode roo2 = new TreeNode(3);
        root.right = roo1;
        roo1.left = roo2;

        List<Integer> list = new ArrayList<>();
        preorderTraversal(root, list);
        for (Integer i : list) {
            System.out.println(i);
        }


    }


    public static List<Integer> inorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) return list;
        inorderTraversal(root.left, list);
        list.add(root.val);
        inorderTraversal(root.right, list);
        return list;
    }

    public static List<Integer> inorderTraversal1(TreeNode root, List<Integer> list) {
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        //while循环
        while (root!=null || !stack.isEmpty()){
            //先将左子树入栈
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }


    public static List<Integer> preorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) return list;
        list.add(root.val);
        preorderTraversal(root.left, list);
        preorderTraversal(root.right, list);
        return list;
    }

    public static List<Integer> preorderTraversal1(TreeNode root, List<Integer> list) {
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        //while循环
        while (root!=null || !stack.isEmpty()){
            //先将左子树入栈
            while (root!=null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return list;
    }



    public static List<Integer> postorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) return list;

        postorderTraversal(root.left, list);
        postorderTraversal(root.right, list);
        list.add(root.val);
        return list;
    }

    /**
     * （1）一直向左遍历，将节点入栈，直到到达最左边；
     * （2）取栈顶节点，讨论是否可以访问当前出栈节点；
     * （3）如果 t == NULL 或者 t == last，则可以访问，并用 last 记录当前访问的节点，将 t 置NULL；
     * 否则不能访问，将当前出栈节点重新入栈，转而前往右子树。
     *
     * 停止迭代的条件和前序遍历、中序遍历一样，也是 t == NULL 并且 stack为空。
     * @param root
     * @param list
     * @return
     */
    public static List<Integer> postorderTraversal1(TreeNode root, List<Integer> list) {
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();

        //标记上一个访问的节点
        TreeNode last = null;
        //while循环
        while (root!=null || !stack.isEmpty()){
            //先将左子树入栈
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            //左节点已经被访问过且右节点为空，或者右节点是上一次访问的节点。
            if (root.right == null || root.right == last){
                list.add(root.val);
                last = root;
                root = null;
            }else {
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }



    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
